/**
 * RSA加密算法的TypeScript实现
 * 完全手写，不依赖任何现有的加密API
 * 支持1024、2048、4096位密钥
 * 支持超长字符串的分块加解密
 */

/**
 * 大数运算库 - 处理RSA所需的大整数计算
 */
class BigInt {
  // 以数组形式存储大数，每个元素是一个数字（0-9）
  private digits: number[];
  private isNegative: boolean;

  constructor(value: string | number | BigInt = 0) {
    this.digits = [];
    this.isNegative = false;

    if (value instanceof BigInt) {
      this.digits = [...value.digits];
      this.isNegative = value.isNegative;
    } else if (typeof value === "number") {
      this.isNegative = value < 0;
      value = Math.abs(value);
      if (value === 0) {
        this.digits = [0];
      } else {
        while (value > 0) {
          this.digits.unshift(value % 10);
          value = Math.floor(value / 10);
        }
      }
    } else if (typeof value === "string") {
      if (value.startsWith("-")) {
        this.isNegative = true;
        value = value.substring(1);
      }
      this.digits = value.split("").map((d) => parseInt(d, 10));
      // 移除前导零
      while (this.digits.length > 1 && this.digits[0] === 0) {
        this.digits.shift();
      }
      if (this.digits.length === 1 && this.digits[0] === 0) {
        this.isNegative = false;
      }
    }
  }

  // 复制当前大数
  clone(): BigInt {
    return new BigInt(this);
  }
  // 判断当前数是否为负数
  isNegativeValue(): boolean {
    return this.isNegative;
  }
  toNumber(): number {
    return parseInt(this.toString(), 10);
  }

  // 比较两个大数的大小
  compare(other: BigInt): number {
    if (this.isNegative !== other.isNegative) {
      return this.isNegative ? -1 : 1;
    }

    if (this.digits.length !== other.digits.length) {
      return (
        (this.digits.length - other.digits.length) * (this.isNegative ? -1 : 1)
      );
    }

    for (let i = 0; i < this.digits.length; i++) {
      if (this.digits[i] !== other.digits[i]) {
        return (this.digits[i] - other.digits[i]) * (this.isNegative ? -1 : 1);
      }
    }

    return 0;
  }

  // 判断两个大数是否相等
  equals(other: BigInt): boolean {
    return this.compare(other) === 0;
  }

  // 判断当前大数是否为0
  isZero(): boolean {
    return this.digits.length === 1 && this.digits[0] === 0;
  }

  // 判断当前大数是否为1
  isOne(): boolean {
    return !this.isNegative && this.digits.length === 1 && this.digits[0] === 1;
  }

  // 大数加法
  add(other: BigInt): BigInt {
    if (this.isNegative !== other.isNegative) {
      // 符号不同，转为减法
      const temp = other.clone();
      temp.isNegative = !temp.isNegative;
      return this.subtract(temp);
    }

    const result = new BigInt();
    result.isNegative = this.isNegative;

    let carry = 0;
    let i = this.digits.length - 1;
    let j = other.digits.length - 1;

    while (i >= 0 || j >= 0 || carry > 0) {
      const digit1 = i >= 0 ? this.digits[i] : 0;
      const digit2 = j >= 0 ? other.digits[j] : 0;
      const sum = digit1 + digit2 + carry;

      result.digits.unshift(sum % 10);
      carry = Math.floor(sum / 10);

      i--;
      j--;
    }

    return result;
  }

  // 大数减法
  subtract(other: BigInt): BigInt {
    if (this.isNegative !== other.isNegative) {
      // 符号不同，转为加法
      const temp = other.clone();
      temp.isNegative = !temp.isNegative;
      return this.add(temp);
    }

    // 比较绝对值大小，确保被减数大于减数
    const absThis = this.clone();
    absThis.isNegative = false;
    const absOther = other.clone();
    absOther.isNegative = false;

    let result = new BigInt();
    let larger, smaller;

    if (absThis.compare(absOther) >= 0) {
      larger = this;
      smaller = other;
      result.isNegative = this.isNegative;
    } else {
      larger = other;
      smaller = this;
      result.isNegative = !this.isNegative;
    }

    let borrow = 0;
    let i = larger.digits.length - 1;
    let j = smaller.digits.length - 1;

    while (i >= 0) {
      let digit1 = larger.digits[i] - borrow;
      const digit2 = j >= 0 ? smaller.digits[j] : 0;

      if (digit1 < digit2) {
        digit1 += 10;
        borrow = 1;
      } else {
        borrow = 0;
      }

      result.digits.unshift(digit1 - digit2);

      i--;
      j--;
    }

    // 移除前导零
    while (result.digits.length > 1 && result.digits[0] === 0) {
      result.digits.shift();
    }

    // 如果结果为0，确保符号为正
    if (result.digits.length === 1 && result.digits[0] === 0) {
      result.isNegative = false;
    }

    return result;
  }

  // 大数乘法
  multiply(other: BigInt): BigInt {
    if (this.isZero() || other.isZero()) {
      return new BigInt(0);
    }

    const result = new BigInt();
    result.isNegative = this.isNegative !== other.isNegative;

    // 从右到左遍历第二个数的每一位
    for (let i = other.digits.length - 1; i >= 0; i--) {
      const digit = other.digits[i];
      if (digit === 0) continue;

      // 临时结果
      const temp = new BigInt();
      // 添加适当数量的零（相当于乘以10的幂）
      for (let j = 0; j < other.digits.length - 1 - i; j++) {
        temp.digits.push(0);
      }

      let carry = 0;
      // 乘以当前位
      for (let j = this.digits.length - 1; j >= 0; j--) {
        const product = this.digits[j] * digit + carry;
        temp.digits.unshift(product % 10);
        carry = Math.floor(product / 10);
      }

      if (carry > 0) {
        temp.digits.unshift(carry);
      }

      // 累加到结果中
      result.digits = result.add(temp).digits;
    }

    return result;
  }

  // 大数除法（返回商和余数）
  divide(other: BigInt): { quotient: BigInt; remainder: BigInt } {
    if (other.isZero()) {
      throw new Error("Division by zero");
    }

    const absThis = this.clone();
    absThis.isNegative = false;
    const absOther = other.clone();
    absOther.isNegative = false;

    if (absThis.compare(absOther) < 0) {
      return { quotient: new BigInt(0), remainder: this.clone() };
    }

    const quotient = new BigInt();
    const remainder = new BigInt();

    // 逐位计算商
    for (let i = 0; i < this.digits.length; i++) {
      // 将当前位添加到余数
      remainder.digits.push(this.digits[i]);
      // 移除前导零
      while (remainder.digits.length > 1 && remainder.digits[0] === 0) {
        remainder.digits.shift();
      }

      let count = 0;
      // 计算当前位的商
      while (remainder.compare(absOther) >= 0) {
        remainder.digits = remainder.subtract(absOther).digits;
        count++;
      }

      quotient.digits.push(count);
    }

    // 移除商的前导零
    while (quotient.digits.length > 1 && quotient.digits[0] === 0) {
      quotient.digits.shift();
    }

    // 设置符号
    quotient.isNegative = this.isNegative !== other.isNegative;
    remainder.isNegative = this.isNegative;

    return { quotient, remainder };
  }

  // 大数取模
  mod(other: BigInt): BigInt {
    return this.divide(other).remainder;
  }

  // 大数的幂取模 (a^b mod n)
  modPow(exponent: BigInt, modulus: BigInt): BigInt {
    if (modulus.isOne()) {
      return new BigInt(0);
    }

    let result = new BigInt(1);
    let base = this.clone();
    base.isNegative = false;
    let exp = exponent.clone();
    exp.isNegative = false;

    while (!exp.isZero()) {
      // 如果指数的最低位为1
      if (exp.digits[exp.digits.length - 1] % 2 === 1) {
        result = result.multiply(base).mod(modulus);
      }

      // 指数右移一位（除以2）
      exp = exp.divide(new BigInt(2)).quotient;

      // 底数平方
      base = base.multiply(base).mod(modulus);
    }

    return result;
  }

  // 大数的字符串表示
  toString(): string {
    return (this.isNegative ? "-" : "") + this.digits.join("");
  }

  // 转换为十六进制字符串
  toHexString(): string {
    if (this.isNegative) {
      throw new Error("Cannot convert negative number to hex string");
    }

    if (this.isZero()) {
      return "0";
    }

    let hex = "";
    let num = this.clone();
    const hexChars = "0123456789ABCDEF";

    while (!num.isZero()) {
      const remainder = num.mod(new BigInt(16)).digits[0];
      hex = hexChars[remainder] + hex;
      num = num.divide(new BigInt(16)).quotient;
    }

    return hex;
  }

  // 从十六进制字符串创建大数
  static fromHexString(hex: string): BigInt {
    hex = hex.toUpperCase();
    const hexChars = "0123456789ABCDEF";
    let result = new BigInt(0);
    const base = new BigInt(16);

    for (let i = 0; i < hex.length; i++) {
      const digit = hexChars.indexOf(hex[i]);
      if (digit === -1) {
        throw new Error(`Invalid hex character: ${hex[i]}`);
      }

      result = result.multiply(base).add(new BigInt(digit));
    }

    return result;
  }

  // 生成指定位数的随机大数
  static random(bits: number): BigInt {
    if (bits <= 0) {
      return new BigInt(0);
    }

    let result = new BigInt(0);
    const base = new BigInt(2);

    // 生成随机位
    for (let i = 0; i < bits; i++) {
      // 生成0或1的随机数
      const bit = Math.floor(Math.random() * 2);
      if (bit === 1) {
        // 2^i
        const pow = base.modPow(
          new BigInt(i),
          new BigInt(Number.MAX_SAFE_INTEGER)
        );
        result = result.add(pow);
      }
    }

    return result;
  }
}

/**
 * 素数生成器 - 生成RSA所需的大素数
 */
class PrimeGenerator {
  // Miller-Rabin素性测试
  static isPrime(n: BigInt, k: number = 5): boolean {
    if (n.isZero() || n.isOne()) {
      return false;
    }

    if (n.equals(new BigInt(2))) {
      return true;
    }

    if (n.mod(new BigInt(2)).isZero()) {
      return false;
    }

    // 找到d和r，使得n-1 = 2^r * d
    let d = n.subtract(new BigInt(1));
    let r = 0;

    while (d.mod(new BigInt(2)).isZero()) {
      d = d.divide(new BigInt(2)).quotient;
      r++;
    }

    // 进行k次测试
    for (let i = 0; i < k; i++) {
      // 随机选择a，1 < a < n-1
      const a = BigInt.random(n.toString().length - 1);
      const min = new BigInt(2);
      const max = n.subtract(new BigInt(2));

      let aMod = a.mod(max).add(min);

      // 计算a^d mod n
      let x = aMod.modPow(d, n);

      if (x.isOne() || x.equals(n.subtract(new BigInt(1)))) {
        continue;
      }

      // 连续平方r-1次
      let continueTest = false;
      for (let j = 0; j < r - 1; j++) {
        x = x.modPow(new BigInt(2), n);

        if (x.equals(n.subtract(new BigInt(1)))) {
          continueTest = true;
          break;
        }
      }

      if (continueTest) {
        continue;
      }

      // n不是素数
      return false;
    }

    // n可能是素数
    return true;
  }

  // 生成指定位数的素数
  static generatePrime(bits: number): BigInt {
    if (bits <= 1) {
      throw new Error("Cannot generate prime with less than 2 bits");
    }

    let candidate: BigInt;

    do {
      // 生成随机数
      candidate = BigInt.random(bits);

      // 确保最高位和最低位都是1（奇数且位数正确）
      const mask = new BigInt(1).multiply(
        new BigInt(2).modPow(
          new BigInt(bits - 1),
          new BigInt(Number.MAX_SAFE_INTEGER)
        )
      );
      candidate = candidate.add(mask).add(new BigInt(1));

      // 检查是否为素数
    } while (!this.isPrime(candidate));

    return candidate;
  }
}

/**
 * RSA密钥对
 */
interface RSAKeyPair {
  n: BigInt; // 模数
  e: BigInt; // 公钥指数
  d: BigInt; // 私钥指数
  p?: BigInt; // 素数p
  q?: BigInt; // 素数q
  bits: number; // 密钥位数
}

/**
 * RSA密钥生成器
 */
class RSAKeyGenerator {
  // 生成RSA密钥对
  static generateKeyPair(bits: number = 2048): RSAKeyPair {
    if (bits !== 1024 && bits !== 2048 && bits !== 4096) {
      throw new Error(
        "Unsupported key size. Supported sizes are 1024, 2048, and 4096 bits."
      );
    }

    // 生成两个大素数p和q
    const p = PrimeGenerator.generatePrime(bits / 2);
    const q = PrimeGenerator.generatePrime(bits / 2);

    // 计算模数n = p * q
    const n = p.multiply(q);

    // 计算欧拉函数φ(n) = (p-1) * (q-1)
    const phi = p.subtract(new BigInt(1)).multiply(q.subtract(new BigInt(1)));

    // 选择公钥指数e，1 < e < φ(n) 且 gcd(e, φ(n)) = 1
    let e = new BigInt(65537); // 常用值

    // 确保e与φ(n)互质
    if (e.compare(phi) >= 0 || !this.isCoprime(e, phi)) {
      do {
        e = BigInt.random(16);
        e = e.add(new BigInt(2)); // 确保e > 1
      } while (e.compare(phi) >= 0 || !this.isCoprime(e, phi));
    }

    // 计算私钥指数d，满足 d*e ≡ 1 (mod φ(n))
    const d = this.modInverse(e, phi);

    return {
      n,
      e,
      d,
      p,
      q,
      bits,
    };
  }

  // 判断两个数是否互质
  private static isCoprime(a: BigInt, b: BigInt): boolean {
    return this.gcd(a, b).isOne();
  }

  // 计算最大公约数（欧几里得算法）
  private static gcd(a: BigInt, b: BigInt): BigInt {
    if (b.isZero()) {
      return a;
    }
    return this.gcd(b, a.mod(b));
  }

  // 计算模逆元（扩展欧几里得算法）
  private static modInverse(a: BigInt, m: BigInt): BigInt {
    const extendedGcd = this.extendedGcd(a, m);

    if (!extendedGcd.gcd.isOne()) {
      throw new Error("Modular inverse does not exist");
    }

    // 确保结果为正数
    let result = extendedGcd.x.mod(m);
    if (result.isNegativeValue()) {
      result = result.add(m);
    }

    return result;
  }

  // 扩展欧几里得算法
  private static extendedGcd(
    a: BigInt,
    b: BigInt
  ): { gcd: BigInt; x: BigInt; y: BigInt } {
    if (b.isZero()) {
      return {
        gcd: a,
        x: new BigInt(1),
        y: new BigInt(0),
      };
    }

    const result = this.extendedGcd(b, a.mod(b));
    const newX = result.y;
    const newY = result.x.subtract(a.divide(b).quotient.multiply(result.y));

    return {
      gcd: result.gcd,
      x: newX,
      y: newY,
    };
  }
}

/**
 * RSA加密/解密实现
 */
class RSA {
  private keyPair?: RSAKeyPair;

  constructor() {
    this.keyPair = undefined;
  }

  // 生成新的密钥对
  generateKeyPair(bits: number = 2048): RSA {
    this.keyPair = RSAKeyGenerator.generateKeyPair(bits);
    return this;
  }

  // 导入公钥
  setPublicKey(n: string, e: string): RSA {
    this.keyPair = {
      n: BigInt.fromHexString(n),
      e: BigInt.fromHexString(e),
      d: new BigInt(0), // 公钥模式下不需要私钥
      bits: n.length * 4, // 假设n是十六进制字符串
    };
    return this;
  }

  // 导入私钥
  setPrivateKey(n: string, e: string, d: string): RSA {
    this.keyPair = {
      n: BigInt.fromHexString(n),
      e: BigInt.fromHexString(e),
      d: BigInt.fromHexString(d),
      bits: n.length * 4, // 假设n是十六进制字符串
    };
    return this;
  }

  // 获取公钥
  getPublicKey(): { n: string; e: string } | null {
    if (!this.keyPair) {
      return null;
    }

    return {
      n: this.keyPair.n.toHexString(),
      e: this.keyPair.e.toHexString(),
    };
  }

  // 获取私钥
  getPrivateKey(): { n: string; e: string; d: string } | null {
    if (!this.keyPair || !this.keyPair.d) {
      return null;
    }

    return {
      n: this.keyPair.n.toHexString(),
      e: this.keyPair.e.toHexString(),
      d: this.keyPair.d.toHexString(),
    };
  }

  // 加密单个块
  private encryptBlock(data: BigInt): BigInt {
    if (!this.keyPair || !this.keyPair.e || !this.keyPair.n) {
      throw new Error("Public key not set");
    }

    // 检查数据是否小于模数
    if (data.compare(this.keyPair.n) >= 0) {
      throw new Error("Data too large for key size");
    }

    // 执行RSA加密: c = m^e mod n
    return data.modPow(this.keyPair.e, this.keyPair.n);
  }

  // 解密单个块
  private decryptBlock(data: BigInt): BigInt {
    if (!this.keyPair || !this.keyPair.d || !this.keyPair.n) {
      throw new Error("Private key not set");
    }

    // 检查数据是否小于模数
    if (data.compare(this.keyPair.n) >= 0) {
      throw new Error("Data too large for key size");
    }

    // 执行RSA解密: m = c^d mod n
    return data.modPow(this.keyPair.d, this.keyPair.n);
  }

  // 计算最大块大小（字节）
  private getMaxBlockSize(): number {
    if (!this.keyPair) {
      throw new Error("Key not set");
    }

    // 最大块大小 = 密钥位数/8 - 11 (PKCS#1 v1.5填充)
    return Math.floor(this.keyPair.bits / 8) - 11;
  }

  // 计算加密后块大小（字节）
  private getEncryptedBlockSize(): number {
    if (!this.keyPair) {
      throw new Error("Key not set");
    }

    // 加密后块大小 = 密钥位数/8
    return Math.floor(this.keyPair.bits / 8);
  }

  // 字符串转BigInt
  private stringToBigInt(str: string): BigInt {
    let result = new BigInt(0);
    const base = new BigInt(256);

    for (let i = 0; i < str.length; i++) {
      const charCode = str.charCodeAt(i);
      const charBigInt = new BigInt(charCode);
      const power = base.modPow(
        new BigInt(str.length - 1 - i),
        new BigInt(Number.MAX_SAFE_INTEGER)
      );
      result = result.add(charBigInt.multiply(power));
    }

    return result;
  }
  toNumber(): number {
    return parseInt(this.toString(), 10);
  }
  // BigInt转字符串
  private bigIntToString(bigInt: BigInt): string {
    let result = "";
    const base = new BigInt(256);
    let num = bigInt.clone();

    while (!num.isZero()) {
      const remainder = num.mod(base).toNumber();
      result = String.fromCharCode(remainder) + result;
      num = num.divide(base).quotient;
    }

    return result;
  }

  // 分块加密字符串
  encrypt(text: string): string {
    if (!this.keyPair || !this.keyPair.e || !this.keyPair.n) {
      throw new Error("Public key not set");
    }

    const maxBlockSize = this.getMaxBlockSize();
    const encryptedBlocks: string[] = [];

    // 分块处理
    for (let i = 0; i < text.length; i += maxBlockSize) {
      const block = text.substring(i, i + maxBlockSize);

      // 字符串转BigInt
      const blockBigInt = this.stringToBigInt(block);

      // 加密块
      const encryptedBlock = this.encryptBlock(blockBigInt);

      // 转换为十六进制并存储
      encryptedBlocks.push(encryptedBlock.toHexString());
    }

    // 连接所有加密块，用分隔符分隔
    return encryptedBlocks.join("|");
  }

  // 分块解密字符串
  decrypt(encryptedText: string): string {
    if (!this.keyPair || !this.keyPair.d || !this.keyPair.n) {
      throw new Error("Private key not set");
    }

    // 分割加密块
    const encryptedBlocks = encryptedText.split("|");
    let decryptedText = "";

    // 处理每个加密块
    for (const encryptedBlock of encryptedBlocks) {
      // 从十六进制恢复BigInt
      const encryptedBlockBigInt = BigInt.fromHexString(encryptedBlock);

      // 解密块
      const decryptedBlock = this.decryptBlock(encryptedBlockBigInt);

      // BigInt转字符串
      decryptedText += this.bigIntToString(decryptedBlock);
    }

    return decryptedText;
  }

  // 加密为Base64
  encryptToBase64(text: string): string {
    const encrypted = this.encrypt(text);
    return this.hexToBase64(encrypted);
  }

  // 从Base64解密
  decryptFromBase64(base64Text: string): string {
    const hexText = this.base64ToHex(base64Text);
    return this.decrypt(hexText);
  }

  // 十六进制转Base64
  private hexToBase64(hex: string): string {
    // 确保十六进制字符串长度为偶数
    if (hex.length % 2 !== 0) {
      hex = "0" + hex;
    }

    let base64 = "";
    const base64Chars =
      "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";

    // 每3个字节(6个十六进制字符)转换为4个Base64字符
    for (let i = 0; i < hex.length; i += 6) {
      const chunk = hex.substring(i, i + 6);

      // 补齐到6个字符
      const paddedChunk = chunk.padEnd(6, "0");

      // 转换为3个字节
      const byte1 = parseInt(paddedChunk.substring(0, 2), 16);
      const byte2 = parseInt(paddedChunk.substring(2, 4), 16);
      const byte3 = parseInt(paddedChunk.substring(4, 6), 16);

      // 转换为4个Base64字符
      const b64_1 = byte1 >> 2;
      const b64_2 = ((byte1 & 3) << 4) | (byte2 >> 4);
      const b64_3 = ((byte2 & 15) << 2) | (byte3 >> 6);
      const b64_4 = byte3 & 63;

      base64 += base64Chars[b64_1];
      base64 += base64Chars[b64_2];
      base64 += base64Chars[b64_3];
      base64 += base64Chars[b64_4];
    }

    // 处理填充
    const padding = hex.length % 6;
    if (padding === 2) {
      base64 = base64.substring(0, base64.length - 2) + "==";
    } else if (padding === 4) {
      base64 = base64.substring(0, base64.length - 1) + "=";
    }

    return base64;
  }

  // Base64转十六进制
  private base64ToHex(base64: string): string {
    const base64Chars =
      "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
    let hex = "";

    // 移除填充字符
    base64 = base64.replace(/=+$/, "");

    // 每4个Base64字符转换为3个字节(6个十六进制字符)
    for (let i = 0; i < base64.length; i += 4) {
      const chunk = base64.substring(i, i + 4);

      // 计算每个Base64字符的索引
      const idx1 = base64Chars.indexOf(chunk[0]);
      const idx2 = base64Chars.indexOf(chunk[1]);
      const idx3 = chunk.length > 2 ? base64Chars.indexOf(chunk[2]) : 0;
      const idx4 = chunk.length > 3 ? base64Chars.indexOf(chunk[3]) : 0;

      // 转换为3个字节
      const byte1 = (idx1 << 2) | (idx2 >> 4);
      const byte2 = ((idx2 & 15) << 4) | (idx3 >> 2);
      const byte3 = ((idx3 & 3) << 6) | idx4;

      // 转换为十六进制
      hex += byte1.toString(16).padStart(2, "0");
      if (chunk.length > 2) {
        hex += byte2.toString(16).padStart(2, "0");
      }
      if (chunk.length > 3) {
        hex += byte3.toString(16).padStart(2, "0");
      }
    }

    return hex;
  }
}

// 导出模块
export { RSA };
export type { RSAKeyPair };
